//把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 
//
// 给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3
//,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为 1。 
//
// 注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], 
//..., a[n-2]] 。 
//
// 
//
// 示例 1： 
//
// 
//输入：numbers = [3,4,5,1,2]
//输出：1
// 
//
// 示例 2： 
//
// 
//输入：numbers = [2,2,2,0,1]
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// n == numbers.length 
// 1 <= n <= 5000 
// -5000 <= numbers[i] <= 5000 
// numbers 原来是一个升序排序的数组，并进行了 1 至 n 次旋转 
// 
//
// 注意：本题与主站 154 题相同：https://leetcode-cn.com/problems/find-minimum-in-rotated-
//sorted-array-ii/ 
// Related Topics 数组 二分查找 👍 640 👎 0

package leetcode.editor.cn;

import java.util.EnumSet;

//leetcode submit region begin(Prohibit modification and deletion)
class SolutionOffer11 {

    public int minArray(int[] numbers) {
        int left = 0, right = numbers.length-1;
        while(left < right){
//            int mid = (left + right) / 2; 这样写有问题,可能越界
            int mid = left + (right-left) / 2;
            if(numbers[mid] > numbers[right]){
                left = mid + 1; //这里加1是因为numbers[mid]必然不可能是最小值
            } else if(numbers[mid] < numbers[right]){
                right = mid; ////这里不加1是因为numbers[mid]有可能是最小值
            } else {
                //由于重复元素的存在，我们并不能确定 \textit{numbers}[\textit{pivot}]numbers[pivot] 究竟在最小值的左侧还是右侧，因此我们不能莽撞地忽略某一部分的元素。我们唯一可以知道的是，由于它们的值相同，所以无论 \textit{numbers}[\textit{high}]numbers[high] 是不是最小值，都有一个它的「替代品」\textit{numbers}[\textit{pivot}]numbers[pivot]，因此我们可以忽略二分查找区间的右端点。
                //
                //作者：LeetCode-Solution
                //链接：https://leetcode.cn/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/solution/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-by-leetcode-s/
                //来源：力扣（LeetCode）
                //著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
                right -= 1;
            }
        }
        return numbers[left];
    }

    /**
     * 跟左端点比较为什么就不行？？？
     *
     * 二分目的是判断 mm 在哪个排序数组中，从而缩小区间。而在 nums[m] > nums[i]nums[m]>nums[i]情况下，无法判断 mm 在哪个排序数组中。本质上是由于 jj 初始值肯定在右排序数组中； ii 初始值无法确定在哪个排序数组中。举例如下：
     *
     * 对于以下两示例，当 i = 0, j = 4, m = 2i=0,j=4,m=2 时，有 nums[m] > nums[i] ，而结果不同。
     * [1, 2, 3, 4 ,5][1,2,3,4,5] 旋转点 x = 0x=0 ： mm 在右排序数组（此示例只有右排序数组）；
     * [3, 4, 5, 1 ,2][3,4,5,1,2] 旋转点 x = 3x=3 ： mm 在左排序数组。
     *
     * 作者：jyd
     * 链接：https://leetcode.cn/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/solution/mian-shi-ti-11-xuan-zhuan-shu-zu-de-zui-xiao-shu-3/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * @param numbers
     * @return
     */
    public int minArray1(int[] numbers) {
        int left = 0, right = numbers.length-1;
        while(left < right){
//            int mid = (left + right) / 2; 最好不要这样写,可能越界
            int mid = left + (right-left) / 2;
            if(numbers[mid] > numbers[left]){
                left = mid+1; //这里加1是因为numbers[mid]必然不可能是最小值
            } else if(numbers[mid] < numbers[left]){
                right = mid; ////这里不加1是因为numbers[mid]有可能是最小值
            } else {
                //由于重复元素的存在，我们并不能确定 \textit{numbers}[\textit{pivot}]numbers[pivot] 究竟在最小值的左侧还是右侧，因此我们不能莽撞地忽略某一部分的元素。我们唯一可以知道的是，由于它们的值相同，所以无论 \textit{numbers}[\textit{high}]numbers[high] 是不是最小值，都有一个它的「替代品」\textit{numbers}[\textit{pivot}]numbers[pivot]，因此我们可以忽略二分查找区间的右端点。
                //
                //作者：LeetCode-Solution
                //链接：https://leetcode.cn/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/solution/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-by-leetcode-s/
                //来源：力扣（LeetCode）
                //著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
                left += 1;
            }
        }
        return numbers[right];
    }

    public static void main(String[] args) {
        new SolutionOffer11().minArray1(new int[]{1,2});
    }
}
//leetcode submit region end(Prohibit modification and deletion)
